"""P13 13.基础提升 Manacher算法、滑动窗口中最大值、单调栈"""


"""
Manacher算法：

Manacher算法要解决的问题：以O(N)的时间复杂度求最长回文子串的长度

每个字符位置i的回文半径
之前位置的最右回文边界R
最右回文边界的中心位置C
位置i相对于中心位置C的镜像位置i'

1、当前位置i不在最右回文边界R内，暴力左右扩来求解
2、当前位置i在最右回文边界R内，且位置i'的回文半径小于位置C的的回文半径时，
位置i的回文半径等于位置i'的回文半径
3、当前位置i在最右回文边界R内，且位置i'的回文半径大于位置C的的回文半径时，
位置i的回文半径为位置i到最右回文边界R的距离
4、当前位置i在最右回文边界R内，且位置i'的回文半径等于位置C的的回文半径时，
位置i从位置i'回文半径外的字符开始左右扩来求解
"""


def pretreatment(string: str) -> str:
    """预处理字符串，1234 -> #1#2#3#4#"""
    result = ""
    index = 0
    for i in range(len(string) * 2 + 1):
        if i % 2:
            result += string[index]
            index += 1
        else:
            result += "#"
    return result


def max_palindrome(string: str) -> int:
    """获取string的最大回文长度"""
    if not string:
        return 0
    string = pretreatment(string)
    half_palindrome = [-1] * len(string)
    center = right = max_len = -1
    for i in range(len(string)):
        half_palindrome[i] = min(half_palindrome[2 * center - i], right - i) \
            if right > i else 1
        while (i + half_palindrome[i] < len(string) and
               i - half_palindrome[i] > -1):
            if string[i + half_palindrome[i]] == string[i - half_palindrome[i]]:
                half_palindrome[i] += 1
            else:
                break
        if i + half_palindrome[i] > right:
            right = i + half_palindrome[i]
            center = i
        max_len = max(max_len, half_palindrome[i])
    return max_len - 1


"""
滑动窗口中的最大值：

滑动窗口的左右边界为L、R
双端队列，从左到右为降序，最右边为最大值

R向右运动，新加的节点i：
1、如果双端队列没值或者节点i的值小于双端队列尾部节点的值，
那么节点i从尾部添加进双端队列。
2、如果节点i的值大于或等于双端队列尾部节点的值，那么双端队列从尾部弹出节点，
直到尾部节点的值大于节点i的值或者双端队列无节点，然后节点i从尾部添加进双端队列
L向右运动，删除的节点i：
1、如果节点i等于双端队列头部的节点，双端队列头部的节点从头部弹出双端队列
"""


def get_max_window(array: list, width: int) -> list:
    """获取宽度为width的窗口移动过程中窗口内的最大值"""
    if not array or width < 1 or len(array) < width:
        return []
    double_queue = list()
    result = list()
    for i in range(len(array)):
        while double_queue and array[double_queue[-1]] <= array[i]:
            double_queue.pop(-1)
        double_queue.append(i)
        if double_queue[0] == i - width:
            double_queue.pop(0)
        if i >= width - 1:
            result.append(array[double_queue[0]])
    return result


"""
单调栈：

单调栈要解决的问题：
对于列表中某个位置的数，求它左右两边最近的比它大的数

对于重复值，可以在栈中放链表处理
求比自身大的数，栈从底到顶是降序

如果待放入的数不破坏单调栈的单调性，这直接放入
否则将单调栈中的数弹出，直到满足单调性时再放入
单调栈中的数在弹出时，待放入的数就是弹出数右侧最近的比它大的数
此时栈顶的数（或者栈顶中链表的最后一个数）就是弹出数左侧最近的比它大的数

列表遍历完了，如果单调栈还有数剩余，接入清算阶段：
将单调栈中的数在弹出，弹出数右侧没有比它大的数
此时栈顶的数（或者栈顶中链表的最后一个数）就是弹出数左侧最近的比它大的数

注意：单调栈底的数没有左侧比它大的数
"""

"""
定义：数组中累积和与最小值的乘积，叫做指标A
给定一个数组，请返回子数组中指标A最大的值

以上问题可以使用单调栈处理
"""
